﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution322
{
    public int CoinChange(int[] coins, int amount)
    {
        int[] dp= new int[amount+1];
       
        for(int i = 1; i <= amount; i++)
        {
            int cur = amount + 1;
            for(int j = 0; j < coins.Length; j++)
            {

                if(i - coins[j] > 0)
                {
                    cur= Math.Min(cur, dp[i - coins[j]] + 1);
                }
                

            }
            dp[i] = cur;

            
        }

       
        return dp[amount]>amount? -1: dp[amount];

    }
}




